# JZ6 旋转数组的最小数字
#
# 描述
# 有一个长度为N的升序数组，比如[1,2,3,4,5]，将它进行旋转，
# 即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。
# 请问，给定这样一个旋转数组，求它的最小值。
#
# 提示:
# 1 <= N<= 10000
# 0 <= rotateArray[i] <= 10000
# 你可以使用O(logN)的时间复杂度通过该题吗?
# 示例1
# 输入：
# [3,4,5,1,2]
# 返回值：
# 1
# 示例2
# 输入：
# [3,100,200,3]
# 返回值：
# 3

# 核心代码模式
# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        l = 0
        r = len(rotateArray)-1 # -1勿忘
        while l<r:  # 二分法左大于等于右结束
            mid = l+(r-l)//2   # 做减法小值不溢出,python特点//整除,用/可能是小数
            if rotateArray[mid] > rotateArray[r]:
                # 中大于右 最小值在右区间 左等于中加一
                l = mid+1
            elif rotateArray[mid] < rotateArray[r]:
                # 中小于右 最小值在左区间 右等于中 （不减一因为中有可能是最小值
                r = mid
            else:
                # 中等于右 不清楚 右减一继续搜索
                r -= 1
        return rotateArray[l]   # 返回坐边值